//
// Created by yanhai on 2021/1/17.
//

#include <iostream>
#include <deque>
#include <stack>

#include "graph.h"

using namespace std;

/**
 * 创建图
 * @param vex 顶点集合 'A'
 * @param arc 边集合 <'A', 'B'>
 * @param weights 权重集合
 */
void
CGraph::CreateGraph(const vector<VexType> &vex,
                    const vector<GArc> &arc,
                    const vector<WeightType> &weights)
{
    int i = 0;
    // 存储顶点，和映射关系
    for (auto it = vex.begin(); it != vex.end(); ++it, ++i) {
        _graph_vex.push_back({i, *it});
        _vex_idx.insert(make_pair(*it, i));
    }
    // 使用空链表初始化边集合
    for (int j = 0; j < i; ++j) {
        _graph_arc.push_back(list<ArcNode>());
    }
    // 插入边（和权重）
    bool has = !weights.empty();
    for (size_t j = 0; j < arc.size(); ++j) {
        InsertArc(arc[j], has ? weights[j] : 0);
    }
}

/**
 * 插入一条边信息
 * @param arc 边
 * @param weight 权重
 * @return
 */
bool CGraph::InsertArc(const GArc &arc, int weight)
{
    // 查出两个顶点的id
    auto iFirst = _get_index(arc.first);
    if (iFirst == -1) return false;
    auto iSecond = _get_index(arc.second);
    if (iSecond == -1) return false;

    // 边表节点 <'A', 'B'>
    ArcNode arcNode{iSecond, weight};

    // 获取边表的list
    auto &vexList = _graph_arc[iFirst]; // 注意是引用
    if (find(vexList.begin(), vexList.end(), arcNode) != vexList.end())
        return false;   // 已存在
    vexList.push_back(arcNode);

    // 如果是无向图，还需要插入 <'B', 'A'>
    if (!_direct) {
        auto &revList = _graph_arc[iSecond];    // 注意是引用
        arcNode.idx = iFirst;

        if (find(revList.begin(), revList.end(), arcNode) != revList.end())
            return false;   // 已存在
        revList.push_back(arcNode);
    }
    return true;
}

/**
 * 修改边的权
 * @param arc 要修改的边
 * @param weight 权
 * @return
 */
bool CGraph::UpdateArcWeight(const GArc &arc, const WeightType &weight)
{
    // 查出两个顶点的id
    auto iFirst = _get_index(arc.first);
    if (iFirst == -1) return false;
    auto iSecond = _get_index(arc.second);
    if (iSecond == -1) return false;

    // 边表节点 <'A', 'B'>
    ArcNode arcNode{iSecond, INF};

    auto &arcList = _graph_arc[iFirst];
    auto it = find(arcList.begin(), arcList.end(), arcNode);
    if (it != arcList.end()) {
        it->weight = weight;
        return true;
    }

    cout << arc.first << " -> " << arc.second << " not exist" << endl;
    return false;
}

/**
 * 对图进行深度优先遍历（不能遍历删除）
 * @param func
 */
void CGraph::DFSTraverse(VisitFunc func) const
{
    // 存储顶点是否被访问过
    vector<bool> visited(VexSize(), false);

    for (int i = 0; i < VexSize(); ++i) {   // 可能存在多个连通分量
        if (!visited[i])
            _dfs_traverse(i, visited, func);
    }
}

/**
 * 对图进行广度优先遍历（不能遍历删除）
 * @param func
 */
void CGraph::BFSTraverse(VisitFunc func) const
{
    // 存储顶点是否被访问过
    vector<bool> visited(VexSize(), false);

    for (int i = 0; i < VexSize(); ++i) {   // 可能存在多个连通分量
        if (!visited[i])
            _bfs_traverse(i, visited, func);
    }
}

/**
 * 迪杰斯特拉 最短路径
 * @param s 开始顶点
 * @param visited 是否被确认过
 * @param dis 距离s的距离
 * @param parent 距离s最短路径时的前一个顶点
 */
void CGraph::Dijkstra(const VexType &s,
                      vector<bool> &visited,
                      vector<WeightType> &dis,
                      vector<int> &parent) const
{
    int iStart = _get_index(s);
    if (iStart == -1) {
        cout << "start not exist" << endl;
        return;
    }

    visited[iStart] = true;
    dis[iStart] = 0;
    parent[iStart] = iStart;

    int i = iStart;
    while (true) {
        // 更新邻接点的距离信息
        auto &arcList = _graph_arc[i];
        for (auto &iter: arcList) {
            if (dis[iter.idx] > dis[i] + iter.weight) {
                dis[iter.idx] = dis[i] + iter.weight;
                parent[iter.idx] = i;
            }
        }
        // 从没有被确认的顶点里面找一个最小的出来
        // min是用来记录最小值，然后和后面的比较，midx是被记录的最小值的顶点索引
        int min = INF, midx = -1;
        for (int j = 0; j < dis.size(); ++j) {
            if (!visited[j] && dis[j] < min) {
                min = dis[j];
                midx = j;
            }
        }

        // 顶点都被确认过了
        if (midx == -1) {
            break;
        }

        // 更新出发点（重新选取点）
        visited[midx] = true;
        i = midx;
    }
}

/**
 * 迪杰斯特拉 最短路径
 * @param s 开始顶点
 * @return 每个顶点的 <距离, 距离最近时的父顶点>
 */
vector<pair<WeightType, int>> CGraph::Dijkstra(const VexType &s) const
{
    vector<pair<WeightType, int>> ret;
    vector<bool> visited(VexSize(), false);

    int iStart = _get_index(s);
    if (iStart == -1) {
        return ret;
    }

    // init ret
    for (int i = 0; i < VexSize(); ++i) {
        ret.emplace_back(INF, -1);
    }

    visited[iStart] = true;
    ret[iStart].first = 0;
    ret[iStart].second = iStart;

    int i = iStart;
    while (true) {
        auto &arcList = _graph_arc[i];
        for (auto &iter: arcList) {
            // 更新邻接点的距离信息
            auto &vex = ret[iter.idx];
            if (vex.first > iter.weight + ret[i].first) {
                vex.first = iter.weight + ret[i].first;
                vex.second = i;
            }
        }

        // 从没有被确认的顶点里面找一个最小的出来
        int min = INF, midx = -1;
        for (int j = 0; j < ret.size(); ++j) {
            if (!visited[j] && ret[j].first < min) {
                min = ret[j].first;
                midx = j;
            }
        }

        if (midx == -1) {
            break;
        }

        i = midx;
        visited[i] = true;
    }

    return ret;
}

list<VexType> CGraph::VexPathMin(const VexType &from, const VexType &to) const
{
    list<VexType> r;    // 这里使用list，而不使用vector，只是想调用r.insert()更高效?
    // 也可以先保存到stack里面，再保存到vector里面，实现逆序的效果

    vector<bool> visited(VexSize(), false);
    vector<WeightType> dis(VexSize(), INF);
    vector<int> parent(VexSize(), -1);

    Dijkstra(from, visited, dis, parent);

    int from_idx = _get_index(from);
    int to_idx = _get_index(to);
    if (!visited[to_idx]) {
        return r;   // 无法从from到达to，不在同一个连通图中
    }

    int i = to_idx;
    while (true) {
        // 也可以直接调用
        r.emplace(r.begin(), _graph_vex[i].data);

        // 到from了。退出
        if (i == from_idx) {
            break;
        }

        i = parent[i];
    }

    return r;
}

//////////////////////// private /////////////////////////

/**
 * 回溯 函数堆栈来实现，实际开发过程，图纵深 尾递归
 * 所有递归 都能转化为 递推
 * @param idx
 * @param visited
 * @param func
 */
void CGraph::_dfs_traverse(int idx, vector<bool> &visited, VisitFunc func) const
{
    assert(!visited[idx]);

    visited[idx] = true;    // 被访问过了
    func(_graph_vex[idx]);  // 调用回调函数

    // 遍历边表节点
    auto &arcList = _graph_arc[idx];
    for (auto &iter : arcList) {
        int next = iter.idx;
        if (!visited[next]) {
            _dfs_traverse(next, visited, func);
        }
    }
}

/**
 * 借助中间队列，实现广度优先遍历
 * @param idx
 * @param visited
 * @param func
 */
void CGraph::_bfs_traverse(int idx, vector<bool> &visited, VisitFunc func) const
{
    deque<int> queue;

    // 当前顶点加入队列
    queue.push_back(idx);
    visited[idx] = true;
    func(_graph_vex[idx]);

    // 消费队列，直到为空
    while (!queue.empty()) {
        int i = queue.front();
        queue.pop_front();

        // 把这个顶点的出度边表加入队列
        auto &arcList = _graph_arc[i];
        for (auto &iter: arcList) {
            int next = iter.idx;
            if (!visited[next]) {
                queue.push_back(next);
                visited[next] = true;
                func(_graph_vex[next]);
            }
        }
    }
}
